package com.cb2.algorithm.leetcode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * <a href='https://leetcode.cn/problems/find-all-the-lonely-nodes'>寻找所有的独生节点(Find All The Lonely Nodes)</a>
 * <p>二叉树中，如果一个节点是其父节点的唯一子节点，则称这样的节点为 “独生节点” 。二叉树的根节点不会是独生节点，因为它没有父节点。</p>
 * <p>给定一棵二叉树的根节点 root ，返回树中 所有的独生节点的值所构成的数组 。数组的顺序 不限 。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例 1：
 *      输入：root = [1,2,3,null,4]
 *                      1
 *                    /   \
 *                   2     3
 *                    \
 *                     <font color='blue'>4</font>
 *      输出：[4]
 *      解释：浅蓝色的节点是唯一的独生节点。
 *          节点 1 是根节点，不是独生的。
 *          节点 2 和 3 有共同的父节点，所以它们都不是独生的。
 *
 *  示例 2：
 *      输入：root = [7,1,4,6,null,5,3,null,null,null,null,null,2]
 *                        7
 *                      /   \
 *                     1     4
 *                    /     /  \
 *                   <font color='blue'>6</font>     5    3
 *                               \
 *                                <font color='blue'>2</font>
 *      输出：[6,2]
 *      输出：浅蓝色的节点是独生节点。
 *      请谨记，顺序是不限的。 [2,6] 也是一种可接受的答案。
 *  示例 3：
 *      输入：root = [11,99,88,77,null,null,66,55,null,null,44,33,null,null,22]
 *                          11
 *                        /   \
 *                       99    88
 *                      /        \
 *                    77          66
 *                   /              \
 *                 55                44
 *                /                    \
 *              33                      22
 *      输出：[77,55,33,66,44,22]
 *      解释：节点 99 和 88 有共同的父节点，节点 11 是根节点。
 *      其他所有节点都是独生节点。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>tree 中节点个数的取值范围是 [1, 1000]。</li>
 *     <li>1 <= Node.val <= 10^6</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/5/16 11:07
 */
public class LC1469FindAllTheLonelyNodes_S {
    static class Solution {
        public List<Integer> getLonelyNodes(TreeNode root) {
            List<Integer> ans = new ArrayList<>();
            //iteration(root, ans);
            recursion(root, ans);
            return ans;
        }

        private void iteration(TreeNode root, List<Integer> resList) {
            Deque<TreeNode> stack = new ArrayDeque<>();
            stack.addLast(root);
            while (!stack.isEmpty()) {
                TreeNode currNode = stack.removeLast();
                if (currNode.left != null && currNode.right != null) {
                    stack.addLast(currNode.right);
                    stack.addLast(currNode.left);
                } else if (currNode.left != null) {
                    resList.add(currNode.left.val);
                    stack.addLast(currNode.left);
                } else if (currNode.right != null) {
                    resList.add(currNode.right.val);
                    stack.addLast(currNode.right);
                }
            }
        }

        public void recursion(TreeNode currNode, List<Integer> resList) {
            if (currNode == null) {
                return;
            }
            if (currNode.left != null && currNode.right != null) {
                recursion(currNode.left, resList);
                recursion(currNode.right, resList);
            }else if (currNode.left!=null){
                resList.add(currNode.left.val);
                recursion(currNode.left, resList);
            } else if (currNode.right != null) {
                resList.add(currNode.right.val);
                recursion(currNode.right, resList);
            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        TreeNode root1 = Generator.buildTree(1, 2, 3, null, 4);
        Printer.printTreeNode(root1);
        Printer.printListInteger(solution.getLonelyNodes(root1));

        TreeNode root2 = Generator.buildTree(7, 1, 4, 6, null, 5, 3, null, null, null, null, null, 2);
        Printer.printTreeNode(root2);
        Printer.printListInteger(solution.getLonelyNodes(root2));

        TreeNode root3 = Generator.buildTree(11, 99, 88, 77, null, null, 66, 55, null, null, 44, 33, null, null, 22);
        Printer.printTreeNode(root3);
        Printer.printListInteger(solution.getLonelyNodes(root3));
    }
}
